/***
 * 给定一个二叉树，找到其最小深度。
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 */

//建立二叉树
class TreeNode {
    constructor( value ){
        this.value = value;
        this.leftNode = null;
        this.rightNode = null;
    }
}


let rootNode = new TreeNode(1);
createBinTree(rootNode, 2, 3);
createBinTree(rootNode.leftNode, 4,5);
createBinTree(rootNode.rightNode, 6);
createBinTree(rootNode.rightNode.leftNode, 7);
function createBinTree( node, leftValue, rightValue ){
    if( leftValue != undefined ){
        node.leftNode = new TreeNode(leftValue);
    }
    if( rightValue != undefined ){
        node.rightNode = new TreeNode(rightValue);
    }
}

//先遍历打印
function display( treeNode ){
    if( treeNode == null ){
        return;
    }
    display( treeNode.leftNode );
    display( treeNode.rightNode );
}
display(rootNode);


//实现1： 深度优先
function getMinDeptWithDeptPreference( node ){
    //表示是叶子节点
    if( node.leftNode == null && node.rightNode == null  ){
        return 1;
    }
    
    let min = Number.MAX_SAFE_INTEGER;
    if( node.leftNode != null ){
        min  = Math.min( getMinDeptWithDeptPreference(node.leftNode), min );
    }

    if( node.rightNode != null ){
        min = Math.min( getMinDeptWithDeptPreference(node.rightNode), min );
    }
    
    return min + 1;
}
let minDept = getMinDeptWithDeptPreference(rootNode);
console.log("minDept: "+minDept);

//实现2： 广度优先
rootNode.deptValue = 1;
let queue = [rootNode];
function getMinDeptWithWidthPrefrence(queue){
    while( queue.length > 0 ){
        let node = queue.shift();
        //遇到第一个节点是左右节点都不存在的情形，那么就是叶子节点
        //此时得到的就是最小深度。
        console.log("[");
        console.log(node.value);
        console.log("]");
        if(node.leftNode == null && node.rightNode == null){
            console.log("最小深度: "+node.deptValue);
            return;
        }
        if( node.leftNode != null ){
            node.leftNode.deptValue = node.deptValue+1;
            queue.push( node.leftNode );
        }
        if( node.rightNode != null ){
            node.rightNode.deptValue = node.deptValue+1;
            queue.push( node.rightNode )
        }

    }
}
getMinDeptWithWidthPrefrence(queue);
